import collections
import bisect

class Solution:
    # 圈复杂度12，提交通过，执行时长击败98.91%
    def hIndex1(self, citations) -> int:
        cnt = collections.Counter(citations)
        sorted_cnt = sorted(cnt, reverse=True)
        pre_sum = []
        sum0 = 0
        for n in sorted_cnt:
            sum0 += cnt[n]
            pre_sum.append(sum0)
        if 0 not in sorted_cnt:
            sorted_cnt.append(0)
            pre_sum.append(pre_sum[-1])
        low = high = -1
        for i, sum1 in enumerate(pre_sum):
            if pre_sum[i] < sorted_cnt[i]:
                high = i
            elif pre_sum[i] == sorted_cnt[i]:
                return sorted_cnt[i]
            else:
                low = i
            if low != -1:
                break
        if high == -1:
            return sorted_cnt[low]
        else:
            return pre_sum[high] if pre_sum[high] > sorted_cnt[low] else sorted_cnt[low]


citations = [3,0,6,1,5]
# citations = [1, 1, 2, 3, 5]
# citations = [100]
# citations = [4, 4, 0, 0]
citations = [2, 3, 2]
tester = Solution()
print(tester.hIndex(citations))

